package 力扣.动态规划.区间DP.背包问题;

import java.util.Scanner;

public class 完全背包问题 {
    //测试平台：https://www.acwing.com/problem/content/3/
    /**
     * 有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
     *
     * 第 i 种物品的体积是 vi，价值是 wi。
     *
     * 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
     * 输出最大价值。
     */
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            // 背包的数目
            int N = sc.nextInt();
            if (N <= 0) {
                break;
            }

            // 容量
            int V = sc.nextInt();

            int[] v = new int[N];
            int[] w = new int[N];
            // 读入每个背包
            for (int i = 0; i < N; i++) {
                v[i] = sc.nextInt();
                w[i] = sc.nextInt();
            }

            System.out.println(Solve(N, V, v, w));
        }
    }

    /**
     * 完全背包为什么是正序？
     */
    private static int Solve(int N, int V, int[] v, int[] w) {
       if (N == 0 || V == 0){
           return 0;
       }
       int[] dp = new int[V + 1];
        for (int i = 0; i < N; i++) {
            for (int j = v[i]; j < V+1; j++) {//为什么正序？从小到大，可以多次使用t
                int preSpace = j - v[i];
                int thisSpace = j;
                dp[thisSpace] = Math.max(dp[thisSpace],dp[preSpace] + w[i]);
            }
        }
        return dp[V];
    }
    private static int Solve2(int N, int V, int[] v, int[] w) {
        if (N == 0 || V == 0){
            return 0;
        }
        int[] dp = new int[V + 1];
        for (int i = 0; i < N; i++) {//通过v[i]更新点集
            for (int j = v[i]; j <= V; j++) {//每个物品可以使用无数次，V作为限制条件
                dp[j] = Math.max(dp[j - v[i]] + w[i],dp[j]);
            }
        }
        return dp[V];
    }
}
